package com.Questions.DP;


/**
 * 接雨水
 */
public class leetcode42 {
    // 方法1 朴素的做法是 对于数组的每一个元素
    // 分别向左和向右扫描并记录左边和右边的最大高度
    // 然后及算法每个下标 位置能接的雨水量 时间复杂度O(n^2)

    // 通过动态规划的 想法 预处理左区间和右区间 最值
    // leftMax[i] 表示下标i及其左边的位置中 height最大值
    // rightMax[i] 表示下标i及其右边的位置中 height 最大值
    // 显然left[0]=height[0] rightMax[n-1]=height[n-1]
    // 1<=i<=n-1 leftMax[i]=max(leftMax[i-1],height[i])
    // 1<=i<=n-1 rightMax[i]=max(rightMax[i+1],height[i])

    // 正向遍历数组 得到leftMax的每一个元素值
    // 反向遍历数组 得到rightMax的每一个元素值
    public int trap(int[] height) {
        int n=height.length;
        if(n==0||n==1){
            return 0;
        }
        int sum=0;
        int[] leftMax=new int[n];
        int[] rightMax=new int[n];
        leftMax[0]=height[0];
        rightMax[n-1]=height[n-1];
        for(int i=1;i<n;++i){
            leftMax[i]=Math.max(leftMax[i-1],height[i]);
            rightMax[n-1-i]=Math.max(rightMax[n-i],height[n-1-i]);
        }
        for(int i=0;i<n;++i){
            sum+=(Math.min(leftMax[i],rightMax[i])-height[i]);
        }
        return sum;
    }

//    public int trap(int[] height) {
//        int n = height.length;
//        if (n == 0) {
//            return 0;
//        }
//
//        int[] leftMax = new int[n];
//        leftMax[0] = height[0];
//        for (int i = 1; i < n; ++i) {
//            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
//        }
//
//        int[] rightMax = new int[n];
//        rightMax[n - 1] = height[n - 1];
//        for (int i = n - 2; i >= 0; --i) {
//            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
//        }
//
//        int ans = 0;
//        for (int i = 0; i < n; ++i) {
//            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
//        }
//        return ans;
//    }
}
